

/*
 * @lc app=leetcode.cn id=633 lang=cpp
 *
 * [633] 平方数之和
 *
 * https://leetcode-cn.com/problems/sum-of-square-numbers/description/
 *
 * algorithms
 * Medium (39.00%)
 * Likes:    343
 * Dislikes: 0
 * Total Accepted:    107K
 * Total Submissions: 274.4K
 * Testcase Example:  '5'
 *
 * 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a^2 + b^2 = c 。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：c = 5
 * 输出：true
 * 解释：1 * 1 + 2 * 2 = 5
 *
 *
 * 示例 2：
 *
 *
 * 输入：c = 3
 * 输出：false
 *
 *
 *
 *
 * 提示：
 *
 *
 * 0 <= c <= 2^31 - 1
 *
 *
 */

// @lc code=start
#include <iostream>
#include <unordered_set>
using namespace std;
class Solution {
public:
    // 暴力解法
    /* bool judgeSquareSum(int c) {
        unordered_set<int> hash;
        int i = 0;
        int res;
        while (pow(i, 2) <= c) {
            res = pow(i, 2);
            hash.insert(res);
            if (hash.find(c - res) != hash.end()) {
                return true;
            }
            else {
                ++i;
            }
        }
        return false;
    } */

    // 双指针解法
    bool judgeSquareSum(int c) {
        long left = 0;
        long right = (int)sqrt(c);
        while (left <= right) {
            long sum = left * left + right * right;
            if (sum == c) {
                return true;
            }
            else if (sum > c) {
                --right;
            }
            else {
                ++left;
            }
        }
        return false;
    }
};
// @lc code=end
